package cn.mayday.algorithms.year2021.month1.深度优先遍历;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Mayday05
 * @date 2021/5/12 15:40
 */
public class Offer034PathSum {

    public static void main(String[] args) {

    }

//    方法总结：典型的二叉树方案搜索问题，使用回溯法解决，其包含 先序遍历 + 路径记录 两部分

    LinkedList<List<Integer>> result = new LinkedList<>(); // 存储最终结果
    LinkedList<Integer> path = new LinkedList<>(); // 存储临时路径

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        // 记录所有可能的结果
        dfs(root, target);
        return result;
    }


    /**
     * 递推工作
     *
     * @param root   根节点
     * @param target 指定目标数值
     */
    public void dfs(TreeNode root, int target) {

        // 步骤一： 终止条件
        if (root == null) {
            return; // 叶子节点，返回
        }


        // 步骤二： 递推工作
        path.add(root.val); // 路径更新，将当前节点值加入路径
        target = target - root.val;

        // 刚好找到结果-先序遍历当前节点
        if (target == 0 && root.left == null && root.right == null) {
            result.add(new ArrayList<>(path));
        }

        // 先序遍历之遍历左子树和右子树
        dfs(root.left, target);
        dfs(root.right, target);

        // 路劲恢复：向上回溯前，将本次放进去的路径参数删除掉（走到这里，说明不是）
        path.removeLast();
    }

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
